package com.tzl.leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    private static final Map<Character, Character> B = new HashMap<>() {{
        put('{', '}');
        put('[', ']');
        put('(', ')');
    }};

    public boolean isValid(String s) {
        char first = s.charAt(0);
        if (!B.containsKey(first) || s.length() % 2 != 0)
            return false;
        Deque<Character> stack = new ArrayDeque<>();
        stack.push(first);
        for (int i = 1; i < s.length(); i++) {
            char c = s.charAt(i);
            if (B.get(c) != null || stack.isEmpty() || !(B.get(stack.peek()) != null && B.get(stack.peek()) == c)) {
                stack.push(c);
            } else {
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}
//leetcode submit region end(Prohibit modification and deletion)
